In 3-D graphics systems, primitives are defined by X, Y and Z coordinates of the primitive, by the normals of the vertices of the primitive, and by the colors of the vertices. A graphics system has been proposed that would utilize a Z pyramid memory element which stores the Z values for a current frame of pixels to test for primitive occlusion. Such a graphics system was proposed in an article entitled “Hierarchical Z-Buffer Visibility”, SIGGRAPH 93, Anaheim, Calif., 1–6 Aug. 1993, by Greene, et al. This article discusses building a Z pyramid from the original Z buffer and using the Z pyramid to test cubes comprised of a plurality of primitives for occlusion culling. This approach makes use of the observation that the cube is hidden with respect to the Z buffer if all of its faces correspond to hidden polygons.
Prior to performing this comparison, the Z pyramid is constructed. The Z pyramid is constructed by starting with pixel-level Z values as the base of the pyramid and by comparing subgroups of adjacent Z values to determine the maximum Z value for each subgroup. The maximum Z value for that subgroup is then stored in the Z buffer for the next level up in the pyramid. For example, if 64 Z values were contained in the Z buffer when the comparison began, the next level up in the pyramid will contain 16 Z values, with each of the 16 Z values corresponding to the maximum Z value of the four pixels compared in the corresponding subgroup in the level below it.
In this next level up, the Z values of each subgroup of four adjacent Z values are compared to determine the maximum Z value for each subgroup and then this maximum Z value is stored in the Z buffer for the next level up in the pyramid. Therefore, for the next level up in the pyramid, the Z buffer will contain four Z values. These four Z values are then compared to determine the maximum Z value, which is stored in the Z buffer for the next level up in the pyramid. This last maximum Z value corresponds to the top of the pyramid.
Once the Z pyramid has been constructed, the Z values for the primitives making up the faces of the cubes are compared beginning at the highest level of the pyramid and working down towards the base of the pyramid. For each primitive, the minimum Z value of the primitive is tested against the levels of the pyramid in a top-to-bottom sequence. If the minimum Z value for the primitive is greater than the pyramid Z value, then the primitive is fully occluded. If all of the primitives making up the faces of the cube are occluded, the cube is occluded and can be discarded. If not, the process continues at each level of the pyramid until the cube is either fully occluded or until the process reaches the level in the Z pyramid at which a primitive is found to be at least partially visible.
Although this approach is capable of simultaneously testing a plurality of primitives instead of individually testing each primitive, this approach does not make any provision for updating the Z pyramid “on the fly”. Once a determination is made that a cube contains a visible primitive, the visible primitive must be scan converted to the pixel level before the Z buffer can be updated and the Z pyramid can be reconstructed.
Accordingly, a need exists for a method and apparatus for updating the Z buffer and reconstructing the Z pyramid on the fly as primitives are processed through the graphics pipeline.